Theory of Computation
Q12.
Consider the following languages: I. \{a^{m}b^{n}c^{p}d^{q}|m+p=n+q, \; where \; m,n,p,q \geq 0 \} II. \{a^{m}b^{n}c^{p}d^{q}|m=n \; and \; p=q, \; where \; m,n,p,q\geq 0 \} III. \{a^{m}b^{n}c^{p}d^{q}|m=n=p \; and \; p\neq q, \; where \; m,n,p,q\geq 0 \} IV. \{a^{m}b^{n}c^{p}d^{q}|mn=p+q, \; where\; m,n,p,q\geq 0\} Which of the languages above are context-free?Q13.
S \rightarrow a S a|b S b| a \mid bThe language generated by the above grammar over the alphabet {a,b} is the set of:Q14.
Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals G_{1}:S\rightarrow aSb|T, T\rightarrow cT|\epsilon G_{2}:S\rightarrow bSa|T,T\rightarrow cT|\epsilon The language L(G_{1})\cap L(G_{2}) isQ15.
Consider the following languages: L_{1}=\{a^{n}b^{m}c^{n+m}:m,n\geq 1\} L_{2}=\{a^{n}b^{n}c^{2n}:n\geq 1\} Which one of the following is TRUE?Q16.
Consider the following languages over the alphabet \Sigma = \{a, b,c\}. Let L_{1}=\{a^{n}b^{n}c^{m}|m,n\geq 0\} and L_{2}=\{a^{m}b^{n}c^{n}|m,n\geq 0\} Which of the following are context-free languages ? I. L_{1}\cup L_{2} II. L_{1}\cap L_{2}Q17.
Consider the following languages over the alphabet \sum =\{0,1,c\}: L_{1}=\{0^{n}|1^{n}|n\geq 0\} L_{2}=\{wcw^{r}|w\in \{0,1\}^{*}\} L_{3}=\{ww^{r}|w\in \{0,1\}^{*}\} Here w^{r} is the reverse of the string w. Which of these languages are deterministic Contextfree languages?Q18.
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. \bar{L_{1}} (complement of L1) is recursive II. \bar{L_{2}} (complement of L2) is recursive III. \bar{L_{1}} is context-free IV. \bar{L_{1}} \cup L_{2} is recursively enumerableQ19.
Which of the following languages are context-free? L_{1}=\{a^{m}b^{n}a^{n}b^{m}|m,n\geq 1\} L_{2}=\{a^{m}b^{n}a^{m}b^{n}|m,n\geq 1\} L_{3}=\{a^{m}b^{n}|m=2n+1\}Q20.
Consider the following types of languages: L_{1}:Regular, L_{2}:Context-free, L_{3}:Recursive, L_{4}:Recursively enumerable. Which of the following is/are TRUE? I. \bar{L}_{3}\cup L_{4} is recursivelyenumerable II. \bar{L}_{2}\cup L_{3} is recursive III. L_{1}^{*}\cup L_{2} is context-free IV. L_{1}\cup \bar{L}_{2} is context-free